package leetcode.problems;

import org.junit.Test;

/**
 * Created by gmwang on 2018/7/25
 */
public class _0822FindBottomLeftTreeValue {
    /**
     * Given a binary tree, find the leftmost value in the last row of the tree.
     *
     * Example 1:
     * Input:
     *
     *     2
     *    / \
     *   1   3
     *
     * Output:
     * 1
     * Example 2:
     * Input:
     *
     *         1
     *        / \
     *       2   3
     *      /   / \
     *     4   5   6
     *        /
     *       7
     *
     * Output:
     * 7
     * Note: You may assume the tree (i.e., the given root node) is not NULL.
     */
    /**
     * @param root
     * @return
     */
    int left = 0;
    int res = 0;
    public int findBottomLeftValue(TreeNode root) {
        if(root != null){
            res = root.val;
            findBottomLeftValueLevel(root,0);
        }
        return res;
    }
    public int findBottomLeftValueLevel(TreeNode root,int index) {
        if(root != null){
            if(root.left != null){
                res = findBottomLeftValueLevel(root.left,index+1);
            }
            if(root.right != null){
                res = findBottomLeftValueLevel(root.right,index+1);
            }
            if(index > left){
                left = index;
                res = root.val;
            }
        }
        return res;
    }
    @Test
    public void test() {
//        TreeNode treeNode1 = new TreeNode(2);
//        TreeNode treeNode1L = new TreeNode(1);
//        TreeNode treeNode1R = new TreeNode(3);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode1L = new TreeNode(2);
        TreeNode treeNode1R = new TreeNode(3);
        TreeNode treeNode1LL = new TreeNode(4);
        TreeNode treeNode1LR = new TreeNode(5);
        TreeNode treeNode2R = new TreeNode(6);
        TreeNode treeNode3R = new TreeNode(7);
        treeNode1.left = treeNode1L;
        treeNode1.right = treeNode1R;
        treeNode1L.left = treeNode1LL;
        treeNode1L.right = treeNode1LR;
        treeNode1R.right = treeNode2R;
        treeNode1LR.left = treeNode3R;

//        TreeNode treeNode1LLL = new TreeNode(5);
//        TreeNode treeNode1LLR = new TreeNode(3);
//        TreeNode treeNode1RLL = new TreeNode(9);
//        TreeNode treeNode1RLR = new TreeNode(1);
//        TreeNode treeNode1RRL = new TreeNode(2);
//        TreeNode treeNode1RRR = new TreeNode(3);
//        treeNode1LL.left = treeNode1LLL;
//        treeNode1LL.right = treeNode1LLR;
//        treeNode1LR.left = treeNode1RLL;
//        treeNode1LR.right = treeNode1RLR;
//        treeNode2R.left = treeNode1RRL;
//        treeNode2R.right = treeNode1RRR;


//        TreeNode treeNode1 = new TreeNode(Integer.MIN_VALUE);
//        TreeNode treeNode1L = new TreeNode(Integer.MIN_VALUE);
//        TreeNode treeNode1R = new TreeNode(5);
//        TreeNode treeNode1LL = new TreeNode(-36 );
//        TreeNode treeNode1LR = new TreeNode(2);
//        TreeNode treeNode2L = new TreeNode(4);
//        TreeNode treeNode2R = new TreeNode(6);
//        TreeNode treeNode3R = new TreeNode(3);
//        treeNode1.left = treeNode1L;
//        treeNode1.right = treeNode1R;
//        treeNode1L.left = treeNode1LL;
//        treeNode1L.right = treeNode1LR;
//        treeNode1R.right = treeNode2R;
//        treeNode1R.left = treeNode2L;
//        treeNode1LR.right = treeNode3R;
        int res = findBottomLeftValue(treeNode1);
        System.out.println(res);
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}
